package com.major.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Graph {
    //private ArrayList<String> vertexList;
    private Vertex[] vertexList;            // 顶点
    private int currentSize;
    private int[][] matrixOfGraph;          // 图对应的邻接矩阵
    //private int edgeNum;                    // 边数量
    private Stack<Integer> vertexStack = new Stack<>();
    private int currentIndex;

    // 构造
    public Graph(int size) {
        matrixOfGraph = new int[size][size];
        vertexList = new Vertex[size];
        //edgeNum = 0;
    }

    /**
     * 加入顶点
     *
     * @param vertex
     */
    public void addVertex(Vertex vertex) {
        vertexList[currentSize++] = vertex;

    }

    /**
     * 添加边
     *
     * @param v1
     * @param v2
     */
    public void addEdge(String v1, String v2) {
        int index1 = 0;
        for (int i = 0; i < vertexList.length; i++) {
            if (vertexList[i].getValue().equals(v1)) {
                index1 = i;
            }
        }
        int index2 = 0;
        for (int i = 0; i < vertexList.length; i++) {
            if (vertexList[i].getValue().equals(v2)) {
                index2 = i;
            }
        }

        matrixOfGraph[index1][index2] = 1;
        matrixOfGraph[index2][index1] = 1;

    }

    // 显示邻接矩阵
    public void showGraph() {
        for (int[] ints : matrixOfGraph) {
            System.out.println(Arrays.toString(ints));
        }
    }

    // 深度优先遍历
    public void dfs() {
        // 第0个
        vertexList[0].setVisited(true);
        System.out.println(vertexList[0]);
        vertexStack.push(0);

        // 遍历
        out:
        while (!vertexStack.isEmpty()) {
            for (int i = currentIndex + 1; i < vertexList.length; i++) {
                //
                if (matrixOfGraph[currentIndex][i] == 1 && !vertexList[i].isVisited()) {
                    vertexStack.push(i);
                    vertexList[i].setVisited(true);
                    System.out.println(vertexList[i]);
                    continue out;
                }
            }
            vertexStack.pop();
            if (!vertexStack.isEmpty()) {
                currentIndex = vertexStack.peek();
            }
        }
    }
}
